The present invention relates to storage of data in nonvolatile memories such as flash memories and, more particularly, to a method of reading data stored in a flash memory by reading both hard bits and soft bits and then jointly decoding all the read bits.
Originally, flash memories stored only one bit per cell. Flash memories that store two bits per cell now are available commercially, and flash memories that store more than two bits per cell are being developed. Flash memories that store one bit per cell are called “Single Level Cell” (SLC) memories. Flash memories that store more than one bit per cell are called “Multi Level Cell” (MLC) memories.
FIG. 1 illustrates how a bit pattern of three bits is stored in a MLC memory that is capable of storing three bits per cell.
A flash memory cell is a transistor with two gates: a conventional control gate and a floating gate. Data are written to the cell by injecting electrons into the floating gate. These injected electrons oppose the “reference” voltage that is applied to the control gate, and the cell does not conduct unless the reference voltage is sufficiently high to overcome the charge on the floating gate. The lowest reference voltage that is sufficiently high to overcome the charge on a flash memory cell's floating gate is called the cell's “threshold voltage” herein.
The threshold voltage of a flash memory cell is in a range, called the “voltage window”, from a minimum value Vmin to a maximum value Vmax. For historical reasons, writing data to a flash cell is called “programming” the flash cell. This is done by applying voltage pulses to the cell, to inject electrons from the cell's silicon substrate through the cell's oxide layer into the cell's floating gate, until the threshold voltage of the cell is higher than a “verify” voltage level associated with representation of the desired bit pattern. (The verify voltage level is called a “verify” voltage level because programming the cell includes verifying that the cell's threshold voltage exceeds this level.) In a three-bit-per-cell memory, the voltage window is divided into eight voltage bands: from Vmin to V1, from V1 to V2, from V2 to V3, from V3 to V4, from V4 to V5, from V5 to V6, from V6 to V7 and from V7 to Vmax. A threshold voltage within one of the voltage bands represents a bit pattern as shown in FIG. 1: a threshold voltage between Vmin and V1 represents the bit pattern “111”, a threshold voltage between V1 and V2 represents the bit pattern “110”, etc. In general, the voltage window of a m-bit-per-cell memory is divided into 2m voltage bands.
To read a flash cell, the threshold voltage of the flash cell is compared to the reference voltages that define the voltage bands. (These reference voltage levels also are called “read voltage levels”, or “read levels” for short.) In the case of some flash memories (hereinafter called “type 1” memories), reading a cell that stores a bit pattern of m bits requires m such comparisons. For example, when m=3, as illustrated in FIG. 1, the cell's threshold voltage first is compared to V4. Depending on the outcome of that comparison, the cell's threshold voltage is compared to either reference voltage V2 or reference voltage V6. Depending on the outcome of the second comparison, the cell's threshold voltage is compared to either reference voltage V1 or reference voltage V3 or reference voltage V5 or reference voltage V7. Note that this comparison does not assume prior knowledge of the cell's threshold voltage: circuitry in the flash memory returns a signal indicating whether the cell's threshold voltage is higher or lower than the reference voltage to which it is being compared.
In the case of some other flash memories (hereinafter called “type 2 memories”), the threshold voltage values of all the cells that are read collectively are compared to all 2m−1 reference voltages between Vmin and Vmax.
In a collection of flash cells, the threshold voltages of the cells are distributed statistically around the centers of their respective voltage bands. FIG. 1 shows the cell's threshold voltages in the first voltage band distributed according to a distribution curve 10, the cell's threshold voltages in the second voltage band distributed according to a distribution curve 12, the cell's threshold voltages in the third voltage band distributed according to a distribution curve 14, the cell's threshold voltages in the fourth voltage band distributed according to a distribution curve 16, the cell's threshold voltages in the fifth band distributed according to a distribution curve 18, the cell's threshold voltages in the sixth band distributed according to a distribution curve 20, the cell's threshold voltages in the seventh band distributed according to a distribution curve 22 and the threshold voltages in the eighth band distributed according to a distribution curve 24. There are several reasons for the finite widths of these distributions:
1. The programming process is a stochastic one that relies on inherently stochastic processes such as quantum mechanical tunneling and hot injection.
2. The precision of the read/program circuitry is finite and is limited by random noise.
3. In some flash technologies, the threshold voltage of a cell being read is affected by the threshold voltages of neighboring cells.
4. Chip-to-chip variations and variations in the manufacturing process cause some cells to behave differently than other cells when read/programmed.
In addition, the cell threshold voltage distributions tend to change over time, as follows:
1. As a flash memory is programmed and erased, the sizes of the voltage window and the voltage bands tend to change. These phenomena limit the number of times a MLC flash memory can be erased and re-programmed.
2. The threshold voltage of a flash cell that is not programmed for a long time tends to drift downward (to the left in FIG. 1). This phenomenon limits the time that data can be reliably retained in a flash memory.
The voltage bands of a flash cell should be designed to be wide enough to accommodate all these phenomena, but not too wide. A voltage band that is too narrow, relative to the associated threshold voltage distribution curve and relative to the drift of that curve over time, leads to an unacceptably high bit error rate. Making the voltage bands very wide relative to the associated threshold voltage distributions limits the number of bits in the bit patterns that can be stored reliably in the flash cell. In practice, flash memories are designed to have one error per 1014-1016 bits read. Some flash technologies are unable to achieve this error rate while storing the desired number of bits per cell. Some flash memories based on such technology use error correction circuits to compensate for their high intrinsic error rates. Some NAND flash manufacturers have instructed their customers to incorporate error-correcting code in their applications.
Reference voltages, such as the reference voltages illustrated in FIG. 1, that demark the boundaries of the voltage bands inside the voltage window, are termed “integral reference voltages” herein. The use, in addition to integral reference voltages, of reference voltages that lie within voltage bands, has been proposed, e.g. by Ban, U.S. Pat. No. 7,023,735 and by Guterman et al., U.S. Pat. No. 6,751,766; such reference voltages are termed “fractional reference voltages” herein. Note that the voltages that define the voltage window itself (Vmin and Vmax in FIG. 1) are not considered reference voltages herein.
FIG. 2 is FIG. 1 with the addition of eight fractional reference voltages, V0.5, V1.5, V2.5, V3.5, V4.5, V5.5, V6.5 and V7.5, in the centers of their respective voltage bands. In general, a flash cell for storing m bits has 2m voltage bands and so has 2m−1 integral reference voltages. For example, in the case of a type 1 flash memory whose cells are read with m comparisons of a flash cell's threshold voltage to m of the 2m−1 integral reference voltages, reading such a flash cell may also include comparing the flash cell's threshold voltages to one or more of the fractional voltages that lie between V1 and V2m−1. For example, the last two comparisons of the flash cell's threshold voltage to the integral reference voltages V1 through V2m−1 generally are to two consecutive such integral reference voltages. The fractional reference voltage to which the cell's threshold voltage then is compared typically lies between those two consecutive integral reference voltages.
In the case of a type 2 flash memory whose cells are read by comparing the cells' threshold voltages to all 2m−1 integral reference voltages, it may be necessary to compare the cells' threshold voltages to most or all of the fractional reference voltages that are defined to lie within the voltage bands.
The hardware that is used to compare a cell's threshold voltage to fractional reference voltages is the same as the analog-to-digital hardware that is used in the prior art to compare a cell's threshold voltage to integral reference voltages, for example a voltage comparator.
The information obtained by comparing the threshold voltages of flash cells only to integral reference voltages often is called “hard bits”. The additional information obtained by also comparing the threshold voltages of the flash cells to fractional reference voltages often is called “soft bits”. This terminology is used herein. For example, determining that the threshold voltage of one of the cells of FIG. 1 lies between V1 and V2 provides the information that the cell stores the hard bits “110”. Determining that the threshold voltage of the cell lies between V1 and V1.5 or between V1.5 and V2 provides an additional soft bit of information. Whether this soft bit is called “1” or “0” is arbitrary, but the usual convention is to follow the convention illustrated in FIG. 1 and associate “1” bits with low fractional reference voltages and “0” bits with high fractional reference voltages. So the soft bit obtained by determining that the cell's threshold voltage is between V1 and V1.5 is “1” and the soft bit obtained by determining that the cell's threshold voltage is between V1.5 and V2 is “0”.
As noted above, for historical reasons, the process of writing hard bits to one or more flash cells is called “programming” the cells. The existence of the phenomena described above that give rise to cell threshold voltage distributions and that cause these distributions to change over time implies that when a flash cell is read there is a small but finite probability that the hard bits that are read are not the hard bits with which the cell was programmed. Therefore, it is conventional to write data to a flash memory by programming the cells of the memory with codewords, determined according to an error-correcting code (ECC), that represent the data redundantly. The techniques of “encoding” information into codewords can be classified within two different methods. The first method, called “systematic” encoding, appends redundancy symbols to information to form a codeword. In a systematic codeword, the bits that correspond to the information always are distinguishable from the redundancy bits. The second method, called “nonsystematic” encoding, encodes the information as codewords that are functions of the information and in which it is not possible to identify bits that correspond to the information bits. When flash cells that have been programmed with codewords are read, the results of the reading may not be identical to the codewords with which the cells were programmed. Therefore, the results of such reading are called herein “representations” of the codewords with which the cells were programmed. The process of recovering, from a representation of a codeword, the information bits from which the codeword originally was constructed, is called “decoding” the representation of the codeword to obtain a valid codeword that hopefully is the original codeword. Applying a well-designed ECC decoding algorithm to a representation of a codeword recovers the information from which the codeword originally was constructed, even if some of the bits of the representation of the codeword are not the same as the corresponding bits of the codeword.
In the Ban patent, soft bits are used by the ECC module for estimating the reliability of hard bits. In the Guterman et al. patent, soft bits are used by the ECC module to resolve ambiguities in deciding which hard bits should be corrected. There also are prior art communication systems that use similar approaches to overcome channel noise: extra high-resolution bits, that are analogous to the “soft bits” defined above, are used to improve the decoder's error correction performance.
Another way of classifying an ECC decoding algorithm is according to whether the algorithm is a “hard” decoding algorithm or a “soft” decoding algorithm. The input to a “hard” decoding algorithm is just the value of the codeword bits themselves, as read (or as received, in the case of a communication channel). The input to a “soft” decoding algorithm is, for each bit of the codeword, a probability measure that the bit that has been read (or received) is the same as the bit that was written (or transmitted). Often, this probability is expressed as a log likelihood ratio (LLR), i.e., the logarithm of the ratio of the probability that the bit that was written (or transmitted) was “0” to the probability that the bit that was written (or transmitted) was “1”, given the read threshold voltage. Soft decoding algorithms are described e.g. in George C. Clark, Jr. and J. Bibb Cain, Error Correction Coding for Digital Communications (Springer, 1981), in S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications (Prentice-Hall, 1983) and in Branka Vucetic and Jinhong Yuan, Turbo Codes: Principles and Applications (Kluwer, 2000).
Heretofore, soft decoding ECC algorithms have been used almost exclusively in contexts other than data storage systems, for example, in signal processing fields such as communications, voice coding and image processing. The majority of academic research on ECC is done in the context of communications. Indeed, the three prior art references cited above on soft decoding are directed at the use of soft ECC algorithms in communication. The ECC decoders of the Ban patent and of the Guterman et al. patent are hard decoders: the soft bits are used only to provide qualitative information about the hard bits. Only recently has the use of soft decoders been proposed, in co-pending U.S. patent application Ser. No. 11/514,182, to decode hard bit representations of codewords read from nonvolatile memories such as flash memories. Heretofore, soft decoding has not been used in conjunction with soft bits to decode representations of codewords read from nonvolatile memories such as flash memories.